package LeetCode.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 两个排序数组的中位数
 * 思路：先合并数组
 * @author: leiwenkang02@meituan.com
 * @date: 2018/8/28
 * @time: 19:34
 */
public class Test04寻找两个正序数组的中位数 {
    public static void main(String[] args) {
        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println(findMedianSortedArrays(nums1, nums2));

    }
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int count = len1 + len2;
        boolean even = false;
        if (count % 2 == 0) {
            even = true;
        }

        List<Integer> numList = new ArrayList<>();
        int index1 = 0;
        int index2 = 0;
        int loop = 0;
        while (loop <= (count / 2) && index1 < len1 && index2 < len2) {
            if (nums1[index1] < nums2[index2]) {
                numList.add(nums1[index1]);
                index1++;
            } else {
                numList.add(nums2[index2]);
                index2++;
            }
            loop++;
        }

        while (index1 < len1 && loop <= (count / 2)) {
            numList.add(nums1[index1]);
            index1++;
            loop++;
        }

        while (index2 < len2 && loop <= (count / 2)) {
            numList.add(nums2[index2]);
            index2++;
            loop++;
        }
        if (even) {
            Double a = new Double(numList.get(loop - 1));
            Double b = new Double(numList.get(loop - 2));
            return  (a + b) / 2;
        } else {
            return numList.get(loop - 1);
        }

    }
}
